package com.wsx.third;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by wangshunxi on 2022/6/2.
 * e-mail: wsr12240512@163.com
 * phone: 13388071923
 */

public class Main0282a {

    public static void main(String[] args) {
        Main0282a main0282a = new Main0282a();
        List<String> stringList = main0282a.addOperators("012403", 6);
        System.out.println(stringList.toString());
        System.out.println(main0282a.count);

    }

    private List<String> result;
    private char[] nums;
    private int target;
    private int count = 0;

    public List<String> addOperators(String num, int target) {
        this.result = new ArrayList<>(1 << 3);
        this.nums = num.toCharArray();
        this.target = target;
        backtrace(0, 0, 0, new ArrayList<>(1 << 3));
        return result;
    }

    private void backtrace(int index, long preNumber, long correct, List<String> store) {
        count++;
        if (index == nums.length) {
            if (correct == target) {
                StringBuilder builder = new StringBuilder();
                store.forEach(builder::append);
                result.add(builder.toString());
            }
            return;
        }
        for (int i = index; i < nums.length; ++ i) {
            if (i != index && nums[index] == '0') break;
            long number = Long.parseLong(new String(nums, index, i-index+1));
            if (index == 0) {
                store.add(String.valueOf(number));
                backtrace(i+1, number, number, store);
                store.remove(store.size()-1);
            } else {
                store.add("+" + number);
                backtrace(i+1, number, correct+number, store);
                store.remove(store.size()-1);

                store.add("-" + number);
                backtrace(i+1, -number, correct-number, store);
                store.remove(store.size()-1);

                store.add("*" + number);
                long multi = preNumber*number;
                backtrace(i+1, multi, correct-preNumber+multi, store);
                store.remove(store.size()-1);
            }
        }
    }
}
